1. Field of the Invention
The present invention relates to a connection scheduler for a crossbar switch and, more particularly, pertains to a scheduling technique for an input-buffered Nxc3x97N non-blocking crossbar switch which can be enhanced to support rate-based traffic scheduling. Simulation results indicate that the rate-based scheduling mechanism of this invention provides an excellent average bounding of the difference between requested service delay and actual service delay through the switch fabric. This behavior is robust to a large variety of traffic patterns as long as the requested traffic load is no greater than a large fraction of unity, xcex3. These empirical results are described with reference to the simulations discussed in the Detailed Description of the Preferred Embodiments.
2. Description of the Related Art
A variety of connection schedulers are known in the art. Each employs one or several scheduling policies. These policies range from simple and practical schemes such as Strict Priority, Round Robin, or Weighted Round Robin, to more elaborate schemes such as Weighted Fair Queuing. There are also many variations of these policies and other policies known in the literature.
A few of the typical performance metrics used to compare the various scheduling methods are jitter and latency of data delivery, fairness of arbitration, and scalability of port count and port bandwidth. Simpler scheduling methods provide only best effort delivery of traffic, while other more complex methods allow traffic flows to establish contracts that establish certain performance guarantees with the network. Typical of these guarantees is the provision of a minimum bandwidth capacity to a traffic flow. Slightly more elaborate traffic contracts may also offer a maximum bounding of cell delivery jitter or delay.
The present invention is a component of a crossbar data switch. Such a switch must have several components. It must have multiple network interfaces. It must have some amount of data buffering at the ingress of the switch. This buffer is able to receive packets at the network interface line rate, and to forward packets at the rate supported by the crossbar switch fabric. When there is contention for an output port of the crossbar from more than one of its input ports, then the buffering at those input ports will be used to store packets for the duration of the mismatch of the receive and forwarding rates caused by contention from other inbound ports for the outbound switch port. If contention is sufficiently long lasting, inbound buffering may become full, and packets will be dropped as a result. There must be an inbound controller to the crossbar that keeps track of how many traffic flows reside in the buffering, where their packets reside, and which outbound port they are destined to. Using this information it must submit forwarding requests to the scheduler, retrieve grants from the scheduler and forward traffic on the granted connection paths. Outbound buffering may also be used to match the crossbar forwarding rate to the outbound network interface line rate. Inbound and outbound controllers may also be responsible for multiplexing traffic from multiple network interfaces into a shared crossbar port, or for demultiplexing traffic from a common outbound switch port to multiple network interface destinations, respectively.
FIG. 1 illustrates a block diagram for an exemplary, preferred crossbar buffered switch 10 according to the present invention. Inbound port controllers 12 buffer data from the physical network link 11, and forward this data across the switch fabric 13. To forward data, the inbound port controllers 12 must participate in cell scheduling which involves the submission of requests and the retrieval of grants. Outbound port controllers 14 receive cells from the fabric 13 and transmit them to a physical network link 15 with minimal buffering being required. An input port controller 12 or output port controller 14 may attach to the fabric 13 in more than one location to improve the physical distribution of I/O bandwidth for a particular implementation. Also shown in FIG. 1 is a connection scheduler 17, herein composed of an active diagonal sequencer 16 and a grant selector 18, which is described below. The grant selector 18 is described in the enclosed pseudo code.
Of these necessary mechanisms for a crossbar data switch, only the connection scheduler is described in detail. The other mechanisms are conventional.
The present invention describes a simple best effort scheduler named Max2d. The present invention also describes a more elaborate scheduler, named Rate2d, that provides minimum average bandwidth guarantees. The Rate2d method is an elaboration of the Max2d method. Both Max2d and Rate2d scale well to implementations with very large port number and per port bandwidth.
In accordance with a specific illustrative embodiment of the present invention, a connection scheduler for an input-buffered Nxc3x97N crossbar switch is presented.
In one aspect of the present invention, the connection scheduler 17 and forwarder 23 are constructed from a two-dimensional cooperative mesh of one-dimensional round robin schedulers. There are 2*N one-dimensional round robin schedules at work, one scheduler 17 associated with each of N input ports 19A-N of the fabric 13 and one scheduler 17 associated with each of N output ports 21A-N of the fabric 13. Although round robin scheduling is well known in the art, the manner in which the schedules employed by this invention cooperate is novel. This cooperative synchronization of the round robin schedulers achieves maximal matching among a set of N2 possible requests from N input ports 19 to N output ports 21. This cooperative synchronization of round robin schedulers is the fundamental basis of this invention and will be referred to as two dimensional round robin scheduling.
Two dimensional round robin scheduling is described in detail as the specification of Max2d. This connection scheduler 17 works in conjunction with a data forwarder 23 as described earlier in this section.
In another aspect of the present invention, the Max2d scheduler is enhanced to implement a rate-based scheduler with deterministic maximal scheduling of connection requests with strict scheduling prioritization derived from requested service delays. This enhanced scheduling method is named Rate2d, and is empirically shown to provide minimum average bandwidth guarantees.
In a broad aspect of the present invention, the connection scheduler for an input-buffered Nxc3x97N non-blocking crossbar switch is adapted to support rate-based traffic scheduling and to provide average-case inter-switch port cell forwarding service delays which are deterministic and well bounded.
In another aspect of the present invention, the connection scheduler is adapted to implement maximal scheduling of connection requests with strict scheduling prioritization derived from requested service delays.
In another aspect of the present invention, the connection scheduler 17 implements a two-dimensionally synchronized round robin arbitration of connection requests stored at the switch elements SEyx (where 0xe2x89xa6yxe2x89xa6Nxe2x88x921 and 0xe2x89xa6xxe2x89xa6Nxe2x88x921) of a crossbar switch fabric 13.
In another aspect of the present invention, the connection scheduler 17 is adapted to implement maximal matching among a set of N2 possible requests from N input ports 19 to N output ports 21 of a crossbar switch fabric 13. Arbitration of a single matching completes in order N time.